/**
 * 求数组每一项左右两边第一个比它大的数
 * @param arr 
 */
const getMinBothSide = (arr: number[]) => {
    const len = arr.length;

    // 边界判断
    if (len === 0) return arr;

    let left: number[] = [], // 距离左边的最大
        right: number[] = [], // 距离右边的最大
        stack: number[] = []; // 模拟栈

    // 初始化数组
    for (let i = 0; i < len; i++) {
        left[i] = -1
        right[i] = -1
    }

    // 遍历
    for (let i = 0; i < len; i++) {
        // 处理右边 (当前元素大于栈顶 并且 栈不为空)
        while (arr[stack[stack.length - 1]] < arr[i] && stack.length > 0) {
            right[stack.pop()!] = i
        }

        // 处理左边 (栈中有元素), 当前元素小于等于栈顶并且占中有值
        if (stack.length > 0) {
            left[i] = stack[stack.length - 1]
        }

        // 将当前索引放入栈中
        stack.push(i)
    }


    console.log(`LEFT: `, left);
    console.log(`RIGHT: `, right)
}




const getMinBothSide2 = (arr: number[]) => {
    const len = arr.length;

    // 边界判断
    if (len === 0) return arr;

    // 1. 存储每一项值和索引的对应项
    const map: Record<number, number> = {}
    for (let i = 0; i < len; i++) {
        map[arr[i]] = i
    }
    let left: number[] = [], // 距离左边的最大
        right: number[] = [], // 距离右边的最大
        stack: number[] = [arr[0]]; // 模拟栈

    // 2.遍历
    for (let i = 1; i < len; i++) {
        // 获取栈顶元素
        const top = stack[stack.length - 1];
        console.log(stack);
        // 当前项小于栈顶
        if (arr[i] < top) {
            // 放入栈中
            stack.push(arr[i])
        } else {
            // 弹出栈, 直到栈顶元素大于arr[i]为止
            let top = stack[stack.length - 1]
            while (top < arr[i]) {
                // 弹出的元素, 右边第一个比它大的就是当前元素arr[i], 左边比它小的就是下一个栈顶元素

                // 只有栈顶小于时, 才弹出栈
                top = stack.pop()!

                right[map[top]] = i

                // 下一个栈顶
                let nextTop = stack[stack.length - 1]
                // 下一个栈顶不为空
                if (nextTop !== undefined) {
                    left[map[top]] = map[nextTop]
                } else {
                    // 下一个栈顶为空, -1表示左边没有比它大的数
                    left[map[top]] = -1;
                }

                top = nextTop;
            }
            // 将当前元素放入栈中
            stack.push(arr[i])
        }
    }

    // 对栈中最后的元素进行处理
    let top: number | undefined;
    while ((top = stack.pop()) !== undefined) {
        // 左边就是下一个栈顶元素, 没有就默认为空
        left[map[top]] = map[stack[stack.length - 1]] || -1

        // 右边不存在
        right[map[top]] = -1
    }

    console.log(`LEFT: `, left);
    console.log(`RIGHT: `, right)
}


getMinBothSide([3, 2, 1, 6, 0, 5])